package niuke.tengxyn._2020;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/04/21 08:07
 * <p>
 * 压缩算法
 * 小Q想要给他的朋友发送一个神秘字符串，但是他发现字符串的过于长了，
 * 于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩，
 * 对于字符串中连续的m个相同字符串S将会压缩
 * 为[m|S](m为一个整数且1<=m<=100)，
 * 例如字符串ABCABCABC将会被压缩为[3|ABC]，
 * 现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？
 */
public class _01 {
    public static void main(String[] args) {
        System.out.println(compress("A[2|B[3|C][4|[5|D[6|E][2|F]]]]"));
    }

    public static String compress(String str) {
        Deque<StringBuffer> sStack = new LinkedList<>();
        Deque<Integer> iStack = new LinkedList<>();
        StringBuffer sb = new StringBuffer();
        char[] chars = str.toCharArray();
        for (int i = 0; i < str.length(); i++) {
            if (chars[i] == '[' || chars[i] == '|') {
                continue;
            }
            if (chars[i] == ']') {
                //连接当前需要操作的全部字符串，到上一个数字位截至。上一个数字位用了一个空字符串表示
                while (sStack.size() > 0) {
                    if (sStack.peekLast().length() == 0) {
                        sStack.pollLast();
                        break;
                    }
                    sb = sStack.pollLast().append(sb);
                }
                Integer nowI = iStack.pollLast();
                StringBuffer deep = new StringBuffer();
                //字符串翻倍
                while (nowI > 0) {
                    deep.append(sb);
                    nowI--;
                }
                sStack.offerLast(deep);
                sb = new StringBuffer();
                continue;
            }
            //如果为数字
            if (chars[i] <= '9' && chars[i] >= '0') {
                StringBuilder sbi = new StringBuilder();
                sbi.append(chars[i]);
                while (chars[i + 1] <= '9' && chars[i] >= '0' && i + 1 < str.length()) {
                    i++;
                    sbi.append(chars[i]);
                }
                //数字入栈，字符串入栈
                Integer nowIa = Integer.valueOf(sbi.toString());
                iStack.offerLast(nowIa);
                if (sb.length() != 0) {
                    sStack.offerLast(sb);
                }
                //存入一个空气标志，代表这个数字的位置
                sStack.offerLast(new StringBuffer());
                sb = new StringBuffer();
                continue;
            }
            //字符串
            sb.append(chars[i]);
        }
        //没有乘法，则把栈里面的内容全部连接。
        if (sStack.size() > 0) {
            while (sStack.size() > 0) {
                sb = sStack.pollLast().append(sb);
            }
        }
        return sb.toString();
    }
}
